#
# @lc app=leetcode.cn id=445 lang=python3
#
# [445] 两数相加 II
#


# @lc code=start
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def length(length):
            n = 0
            while length:
                n += 1
                length = length.next
            return n

        n1 = length(l1)
        n2 = length(l2)

        if n1 < n2:
            n1, n2 = n2, n1
            l1, l2 = l2, l1

        def add(l1, l2, n1, n2):
            if not n1 and not n2:
                return 0

            if n1 > n2:
                temp = l1.val + add(l1.next, l2, n1 - 1, n2)
            else:
                temp = l1.val + l2.val + add(l1.next, l2.next, n1 - 1, n2 - 1)
            l1.val = temp % 10
            return temp // 10

        if add(l1, l2, n1, n2):
            l2 = ListNode(1)
            l2.next = l1
            l1 = l2
        return l1


# @lc code=end
